package leetcode101.data_structure;

import java.util.ArrayList;
import java.util.List;
import java.util.PriorityQueue;
import java.util.TreeMap;

/**
 * @author Synhard
 * @version 1.0
 * @class Code10
 * @description 218. 天际线问题
 * 城市的天际线是从远处观看该城市中所有建筑物形成的轮廓的外部轮廓。给你所有建筑物的位置和高度，请返回由这些建筑物形成的 天际线 。
 *
 * 每个建筑物的几何信息由数组 buildings 表示，其中三元组 buildings[i] = [lefti, righti, heighti] 表示：
 *
 * lefti 是第 i 座建筑物左边缘的 x 坐标。
 * righti 是第 i 座建筑物右边缘的 x 坐标。
 * heighti 是第 i 座建筑物的高度。
 * 天际线 应该表示为由 “关键点” 组成的列表，格式 [[x1,y1],[x2,y2],...] ，并按 x 坐标 进行 排序 。
 * 关键点是水平线段的左端点。列表中最后一个点是最右侧建筑物的终点，y 坐标始终为 0 ，仅用于标记天际线的终点。
 * 此外，任何两个相邻建筑物之间的地面都应被视为天际线轮廓的一部分。
 *
 * 注意：输出天际线中不得有连续的相同高度的水平线。例如 [...[2 3], [4 5], [7 5], [11 5], [12 7]...] 是不正确的答案；
 * 三条高度为 5 的线应该在最终输出中合并为一个：[...[2 3], [4 5], [12 7], ...]
 *
 *
 * 输入：buildings = [[2,9,10],[3,7,15],[5,12,12],[15,20,10],[19,24,8]]
 * 输出：[[2,10],[3,15],[7,12],[12,0],[15,10],[20,8],[24,0]]
 * 解释：
 * 图 A 显示输入的所有建筑物的位置和高度，
 * 图 B 显示由这些建筑物形成的天际线。图 B 中的红点表示输出列表中的关键点。
 *
 * 输入：buildings = [[0,2,3],[2,5,3]]
 * 输出：[[0,3],[5,0]]
 *
 * @tel 13001321080
 * @email 823436512@qq.com
 * @date 2021-05-10 10:09
 */
public class Code10 {
    public static void main(String[] args) {

    }

    public List<List<Integer>> getSkyline(int[][] buildings) {
        TreeMap<Integer, List<int[]>> map = new TreeMap<>();

        for (int[] b : buildings) {
            map.putIfAbsent(b[0], new ArrayList<>());
            map.putIfAbsent(b[1], new ArrayList<>());
            map.get(b[0]).add(b);
            map.get(b[1]).add(b);
        }

        PriorityQueue<int[]> maxHeap = new PriorityQueue<>((a, b) -> b[2] - a[2]);

        List<List<Integer>> res = new ArrayList<>();

        for (int pos : map.keySet()) {
            List<int[]> bs = map.get(pos);

            for (int[] b : bs) {
                if (b[0] == pos) {
                    maxHeap.offer(b);
                } else {
                    maxHeap.remove(b);
                }
            }

            if (maxHeap.size() == 0) {
                List<Integer> temp = new ArrayList<>();
                temp.add(pos);
                temp.add(0);
                res.add(temp);
            } else {
                int maxHeight = maxHeap.peek()[2];
                if (res.size() == 0 || res.get(res.size() - 1).get(1) != maxHeight) {
                    List<Integer> temp = new ArrayList<>();
                    temp.add(pos);
                    temp.add(maxHeight);
                    res.add(temp);
                }
            }
        }
        return res;
    }

}
/*
我愿称之为发际线问题而不是天际线问题
首先构建一个treemap
里面存放建筑物的起止对于建筑物的映射
buildings = [[2, 9, 10],[3, 7, 15],[5, 12, 12],[15, 20, 10],[19, 24, 8]]
则treemap中的数据如下：
2 : [2, 9, 10]
3 : [3, 7, 15]
5 : [5, 12, 12]
7 : [3, 7, 15]
9 : [2, 9, 10]
12 : [5, 12, 12]
15 : [15, 20, 10]
19 : [19, 24, 8]
20 : [15, 20, 10]
24 : [19, 24, 8]

之后建立一个优先级队列，往里面仍value，按照高度作为优先级排序
然后遍历treemap
对于 2 : [2, 9, 10]
因为 2 = 2 代表一个建筑物的开始，将他扔进堆中，并且最大高度等于当前建筑物的最大高度，[2, 10]加入结果集

对于 3 : [3, 7, 15]
因为 3 = 3 代表一个建筑物的开始，将他扔进堆中，并且最大高度等于当前建筑物的最大高度，[3, 15]加入结果集

对于 5 : [5, 12, 12]
因为 5 = 5 代表一个建筑物的开始，将他扔进堆中，并且最大高度小于当前建筑物的最大高度，说明他被覆盖了，不能加入结果集

对于 7 : [3, 7, 15]
因为 7 = 7 代表一个建筑物的结束，将他从堆中移除，而移除后发现堆的最大高度变了，说明它的移除改变了天际线，需要把它的最右边以及移除后
的堆的最大的高度加入结果集中，因此将[7, 12]加入结果集

对于 9 : [2, 9, 10]
因为 9 = 9 代表一个建筑物的结束，将他从堆中移除，而移除后发现堆的最大高度没变，说明移除了它之后不会改变天际线，所以不需要加入结果集

对于 12 : [5, 12, 12]
因为 12 = 12 代表一个建筑物的结束，将他从堆中移除，而移除后发现堆是空的了，所以要把它的最右边和0加入结果集中，因此将[12, 0] 加入结
果集

之后以此类推，直到遍历完所有的map
 */